Knuth Morris Pratt (KMP) String Match algorithm

Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function
search(char pat[], char txt[]) that prints all occurrences of pat[] in txt[].
You may assume that n > m.
See: https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/
https://stackoverflow.com/questions/13271856/understanding-knuth-morris-pratt-algorithm

def KMPSearch(pat, txt):
   M = len(pat)
   N = len(txt)
   # create lps[] that will hold the Longest Prefix Suffix
   # values for Pattern
   lps = [0] * M
   j = 0  # index for pat[]

   # Preprocess the pattern (calculate lps[] array)
   computeLPSArray(pat, M, lps)

   i = 0  # index for txt[]
   while i < N:
       if pat[j] == txt[i]:
           i += 1
           j += 1
       if j == M:
           print("Found pattern at index " + str(i - j))
           j = lps[j - 1]
           # mismatch after j matches
       elif i < N and pat[j] != txt[i]:
           # Do not match lps[0..lps[j-1]] characters,
           # they will match anyway
           if j != 0:
               j = lps[j - 1]
           else:
               i += 1

def computeLPSArray(pat, M, lps):
   len = 0  # length of the previous Longest Prefix Suffix
   lps[0]   # lps[0] is always 0
   i = 1

   # the loop calculates lps[i] for i = 1 to M-1
   while i < M:
       if pat[i] == pat[len]:
           len += 1
           lps[i] = len
           i += 1
       else:
           # This is tricky. Consider the example.
           # AAACAAAA and i = 7. The idea is similar
           # to search step.
           if len != 0:
               len = lps[len - 1]
               # Also, note that we do not increment i here
           else:
               lps[i] = 0
               i += 1

Test

txt = "AABAACAADAABAABA"
pat = "AABA"
KMPSearch(pat, txt)

Output:
 Found pattern at index 0
 Found pattern at index 9
 Found pattern at index 12